package or;

public class T0200 {
    boolean[][] hasPass;
    char[][] grid;
    int n;
    int m;

    public int numIslands(char[][] grid) {
        this.n = grid.length;
        this.m = grid[0].length;
        this.hasPass = new boolean[n][m];
        this.grid = grid;
        int sum = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!hasPass[i][j] && grid[i][j] == '1') {
                    diffuse(i, j);
                    sum++;
                }
            }
        }
        return sum;
    }


    public void diffuse(int a, int b) {
        hasPass[a][b] = true;
        if (a - 1 >= 0 && !hasPass[a - 1][b] && grid[a - 1][b] == '1') diffuse(a - 1, b);
        if (a + 1 < n && !hasPass[a + 1][b] && grid[a + 1][b] == '1') diffuse(a + 1, b);
        if (b - 1 >= 0 && !hasPass[a][b - 1] && grid[a][b - 1] == '1') diffuse(a, b - 1);
        if (b + 1 < m && !hasPass[a][b + 1] && grid[a][b + 1] == '1') diffuse(a, b + 1);
    }
}
